Convex Structures

Blake's Newton

Back

(A) Convex Sets and Convex Hulls
(B) The Separating Hyperplane Theorem
(C) Convex Cones and Inequalities
(D) The Minkowski-Farkas Lemma

Selected References

Appeals to convex stuctures in mathematics are few and far between. Rather than dealing with the particular case of convex sets, much of mathematics prefers to concentrate on more general linear subspaces. However, convex structures are central in modern economics -- particularly with the development of linear programming and the discovery (by economists) of the Separating Hyperplane Theorem in the 1940s - which allowed them to reformulate much of the central tenets of Walrasian economics without unecessary and restrictive differentiability assumptions. Convexity was the organizing principle of mathematical economics - particularly as practiced by those associated with the Cowles Commission (Koopmans, Debreu, Arrow, etc.) throughout the 1950s. The crucial contribution to this transformation was John von Neumann's 1937 paper written through the Vienna Colloquium.

Most of the important mathematical arguments contained here and in the subsequent sections - axiomatic reasoning, convexity arguments, linear systems of inequalities, saddlepoints, programming and duality relationships and fixed-point theorems were all introduced to economics by John von Neumann (1937). Adoption and extension of these tools were relatively swift and revolutionized mathematical economics and drew it away from the "Paretian" use of differential calculus and into axiomatic reasoning. For more reflections on this transformation in mathematical approach, see Debreu (1984, 1986, 1991), Khan (1993), Mirowski and Weintraub (1994) and Weintraub (1985).

(A) Convex Sets and Convex Hulls

We begin with a simple definition:

Convex: the set X Í Rn is a "convex set" if for every x, y Î X and any l Î (0, 1), then l x + (1-l)y Î X.

Now we turn to an often useful theorem:

Theorem: Let {Xn} be a collection of convex sets. Then Ç nXn is a convex set.

Proof: If x, y Î Ç nXn then x, y Î Xn for all n. Since Xn is convex, then for any l Î (0, 1), we have l x + (1-l )y Î Xn for all n. Thus, for any l Î (0, 1), l x + (1-l )y Î Ç nXn.§

It is easy to show that È nXn is not convex.

Convex Hull: If the set co(X) Í Rn is the smallest convex set in Rn containing X, then co(X) is the "convex hull" of X.

Thus, we can readily notice that co(X) is generated by all convex linear combinations of elements of X, i.e. the convex hull of X merely equals all points å i l ixi where xi Î X and l i ³ 0 and å il i = 1.

Theorem: For every non-empty subset X Í Rn, the convex hull of X, co(X), exists.

Proof: Let {Xn} be the collection of all convex sets containing X, i.e. X Í Xn for all Xn. Since Rn is itself convex, then {Xn} is non-empty. From the earlier theorem, we know that the intersection is convex, thus Ç n Xn is convex and itself contains X. Thus, define co(X) = Ç nXn which is the smallest convex set containing X.§

(B) The Separating Hyperplane Theorem (SHT)

The Separating Hyperplane Theorem is merely a version of the Hahn-Banach Theorem for functional analysis - and really states nothing much more complicated than that two convex sets can be separated by a line ("hyperplane") with one of the convex sets lying on one side of it and the other set sitting on the other. However, the importance of the "discovery" of the SHT by economists in the 1940s and 1950s can hardly be overstressed - for in this "separating hyperplane", economists saw "price lines" and in the convex sets they saw the typical sets in economics on which these price lines would sit - those defined by indifference curves, budget constraints, production possibility frontiers, etc. What was merely a supposition before the 1950s - i.e. "there is a set of prices such that..." was now translated into "there is a separating hyperplane..." and thereby confirmed.

Generally, a hyperplane is a linear subspace of one dimension less than the space in which it sits (thus diagramatically, a "hyperplane" is a line drawn in a two-dimensional space or a plane drawn in three-dimensional space). It is defined as follows:

Hyperplane: A given non-zero vector p Î Rn and a scalar c Î R define a "hyperplane" H(p, c) in Rn where:

H(p, c) = {x Î Rn | p·x = c}

Thus, H(p, c) Í Rn is a linear subspace. A hyperplane divides the space into two closed "half-spaces" H³(p, c) = {x Î Rn | p·x ³ c} and H£(p, c) = {x Î Rn | p·x £ c} which are the spaces "above" and "below" the hyperplane respectively. These half-spaces are convex:

Theorem: (Convexity of Half-Spaces) For all non-zero p Î Rn and c Î R, the set H£ = {x Î Rn | p·x £ c} is convex.

Proof: Let x, y Î H£ . Then for all l Î [0, 1], p·(l x + (1-l )y) = l (p·x) + (1-l )(p·y). Since x, y Î H£, then p·x £ c and p·y £ c thus, l (p·x) + (1-l )(p·y) £ l c + (1-l )c = c and thus p·(l x + (1-l )y) £ c. Thus, l x + (1-l )y Î H£ .§

And we can do the same for H³.

Supporting Hyperplane: A hyperplane H is said to be a "supporting hyperplane" to a convex set X if X is contained within one of the halfspaces of H and the boundary of X has points in comon with H, i.e. H is a supporting hyperplane to X if inf{p·x | x Î X} = c (thus X Í X³ ) or sup{p·x | x Î X} = c (thus X Í X£ ).

Separating Hyperplane: Two convex sets, A and B, are "separable by a hyperplane" if there exists a hyperplane H(p, c) such that A and B belong to different half-spaces, i.e. such that A Í {x Î Rn | p·x ³ c} and B Í {x Î Rn | p·x £ c}. They are "strictly separable" if either A Ì {x Î Rn | p·x > c} and/or B Ì {x Î Rn | p·x < c}.

This is easy to visualize diagramatically as in Figure 2.  Let us now turn to the SHT. We first prove that we can separate a convex a point from a non-empty convex set, before proving we can separate two disjoint convex sets.

Theorem: (Separation of Point from Convex Set) Let X be a non-empty and convex set in Rn. Let y Î Xc. Then there exists a vector p Î Rn where p ¹ 0 and inf{px | x Î X} > py (i.e. the sets {y} and X are separable).

Proof: If X is convex, then its closure cl(X) is also convex. Let x° be a boundary point of X such that ||x° - y|| = infxÎ X ||x - y||, i.e. x° is the point in cl(X) closest to y. As cl(X) is convex, then if x Î X, then l x + (1-l )x° Î cl(X) for any l Î (0, 1] - or, simply, x° + l (x - x° ) Î cl(X). But as ||x0 - y|| £ ||x - y|| for all x Î cl(X), then ||x0 - y|| £ ||(x0 + l (x-x0)) - y||

or:

||x0 - y|| £ ||(x0 - y) + l (x-x0)||

Thus squaring:

||x0 - y||2 £ ||(x0 - y) + l (x-x0)||2

But as ||x||2 = x·x, then:

(x0 - y)(x0 - y) £ [(x0 - y) + l (x - x0)]·[(x0 - y) + l (x - x0)]

or:

(x0 - y)(x0 - y) £ (x0 - y)(x0 - y) + 2l (x - x0)·(x0 - y) + l 2(x - x0)(x - x0)

thus:

2l (x - x0)·(x0 - y) + l 2(x - x0)(x - x0) ³ 0

Thus, it must be that (x - x0)·(x0 - y) ³ 0 which implies that x·(x0 - y) ³ x0·(x0 - y). But by the property of inner product, if x0 ¹ y, then (x0 - y)(x0 - y) > 0, and thus x0(x0 - y) > y(x0 - y), thus combining the two inequalities:

x·(x0 - y) ³ x0·(x0 - y) > y(x0 - y)

Define p = (x0 - y), then if p ¹ 0 then the inequalities imply:

x·p ³ x0·p > y·p

thus, inf{x·p | x Î X} ³ x0·p > y·p. Thus, letting c = x0·p, then:

(i) x·p ³ c for all x Î X

(ii) c > y·p for {y}.

Thus, {y} and X are separated by the hyperplane H(p, c) = {x Î Rn | x·p = c}.§

The foregoing proof is illustrated in Figure 1 (where z = l x + (1-l )x0) for two-dimensional Euclidian space (R2).

convex1.gif (5308 bytes)

 

Figure 1 - Separation of Point from Set

We can now turn to the main Separating Hyperplane Theorem:

Theorem: (Separating Hyperplane Theorem) Let X and Y be two non-empty, convex sets in Rn with no interior point in common, then there exists a pair (p c) where p Î Rn ¹ 0 and c Î R such that:

px ³ c    " x Î X

py £ c " y Î Y

i.e. there is a hyperplane H(p, c) which separates X and Y.

Proof: Define X - Y = {x - y Î Rn | x Î X, y Î Y} which is convex. Then, 0 Ï int(X-Y) (if it was, i.e. if 0 Î int(X - Y), then there is an x Î int(X) and y Î int(Y) such that x - y = 0, or simply x = y, i.e. there is an interior point in common). Thus, we can separate 0 from X-Y, i.e. there exists a p Î Rn where p ¹ 0 and a c Î R such that p·(x-y) ³ c and p·0 £ c. As p·0 = 0, then p·(x-y) ³ 0, thus px ³ py for all x Î A and y Î B, or simply there is a c Î R such that px ³ c for all x Î X and py £ c for all y Î Y for all y Î Y. §

An example of this in a two-dimensional space can be seen in Figure 2.

convex2.gif (3553 bytes)

 

Figure 2 - Separation of two convex sets

Of course, there is also a "strict" SHT which is as follows:

Theorem: (Strict SHT) Let X and Y be two closed, convex sets in Rn with no points in common and at least one of which is bounded, then there exists a pair (p c) where p Î Rn ¹ 0 and c Î R such that:

px > c " x Î X

py < c " y Î Y

i.e. there is a hyperplane H(p, c) which strictly separates X and Y.

Proof: Now, X and Y are closed thus, if either X or Y is bounded, then X - Y is closed as well and, as they have no points in common, then 0 Ï X-Y. Consequently, the rest of the proof follows from the previous theorem on the separation of a point 0 from set X-Y.§

(C) Convex Cones and Inequalities

Cone: X is a cone with vertex at the origin if for any x Î X and any scalar a ³ 0, then a x Î X.

Convex Cone: X is a "convex cone" if for any x, y Î X and any scalars a ³ 0 and b ³ 0, then a x + b y Î X.

Thus a convex cone is always convex always contains the origin. See the diagram below for an example in R2.

Spanning: The "convex cone spanned by Y" is the smallest convex cone that contains the set Y, i.e.

C(Y) = {å i l i yi ½ for all i = 1, .., n, l i ³ 0, yi Î Y and n arbitrary}

In Figure 3, X = C(Y), i.e. X is the convex cone spanned by Y.

Dual Cone: The "dual" X* of a convex cone X is the set {p Î Rn | p·x £ 0 for all x Î X}.

An example of the dual X* of the convex cone X is shown in Figure 3, for two-dimensional Euclidian space.

convex3.gif (4083 bytes)

Figure 3 - Convex Cones

The dual convex cone is always closed regardless of whether the original convex cone is closed or not. X** is the dual of the dual convex cone which, obviously, must be related to the original convex cone X. This is as follows:

Theorem: (Closedness of Dual Cone) If X is a convex cone, then X Í X** (where X = X** if and only if X is closed).

Proof: By definition of X*, if x Î X, then for all p Î X*, p·x £ 0. But p·x = x·p, so x·p £ 0, thus x Î X**. Thus, X Í X**. If X is closed, we shall prove also that X** Í X. Now, suppose x Ï X. Since X is closed and convex, then by the Separating Hyperplane Theorem, there is a p Î Rn such that p·y £ p·x for all y Î X. But since X is a cone, then p·y £ 0 £ p·x. Thus, x·p ³ 0. Thus, if p Î X* (i.e. p·y £ 0) then x Ï X** (as x·p ³ 0). Thus, x Ï X Þ x Ï X**, thus X** Í X. Thus, combining with the first part, we see that X = X**.§

(D) The Minkowski-Farkas Lemma

The Minkowski-Farkas Lemma - sometimes only referred to as "Farkas's Theorem" is a highly useful result- particularly in linear programming, where we define primal and dual problems. It is effectively a corrollary of a basic theorem of the "alternative" which is, in turn, based on the Separating Hyperplane Theorem.

Theorem: (Basic Theorem of the Alternative) Let A be a m ´ n real matrix and b Î Rm, then exactly one of the following alternatives is true (but not both). Either:

(i) Ax = b has a non-negative solution x ³ 0.

or

(ii) yA ³ 0 and y·b < 0 has a solution y.

Proof: We go through several steps.

(i) Þ not (ii): Suppose that Ax = b has a non-negative solution x (so (i) holds). Then premultiplying by y, then yAx = yb. Then (ii) cannot hold. If it did, i.e. if yA ³ 0, then we see that yAx ³ 0 because x ³ 0 from (i). But, if so, then it must be that yb ³ 0, which contradicts (ii). Thus, not (ii).

not (i) Þ (ii): Let X be the convex cone spanned by columns a1, .., an of A, i.e.

X = {a Î Rn | a = å il iai, l i ³ 0, i = 1, .., n}

Suppose that Ax = b has no non-negative solution. Then b Ï X. Since X is closed, then by the Separating Hyperplane Theorem, there is a vector y Î Rm such that y·a > y·b for all a Î X. Since X contains the origin, then 0 = y·0 > y·b. Supose that not yA ³ 0. Thus, there is a column in A, say ak such that y·ak < 0. Since X is a cone and ak Î X, then a ak Î X for all a > 0. Thus, for sufficiently large a , then y·(a ak) = a (y·ak) < y·b. But this contradicts separation. Thus, y·ai ³ 0 for all columns ai of A. Thus yA ³ 0. Thus, (ii) holds.§

The Minkowski-Farkas Lemma follows as a corrollary to the above. Namely:

Theorem: (Minkowski-Farkas Lemma) Let A be a m ´ n real matrix with column vectors a1, .., an Î Rm and b Î Rm. Then l ·b ³ 0 for all l Î Rm such that l A ³ 0 if and only if there exists non-negative vector x = (x1, ..., xn) such that Ax = b.

Proof: Since l ·b ³ 0 for all l Î Rm such that l A ³ 0, then there can be no l such that l A ³ 0 and l ·b < 0. But then, by the previous theorem of the alternative, it must be that Ax = b for some non-negative x Î Rn.§

Thus, in short, the Minkowski-Farkas Lemma states that if l ·b ³ 0 for all l such that l A ³ 0 , then Ax = b has a non-negative solution x ³ 0. The applications of the Minkowksi Lemma are numerous - to duality theorems in linear programming, the Kuhn-Tucker theorem and in zero-sum games.

This is, of course, merely a formal result - see Gale (1960: p.44) or Takayama (1974: p.46-7) for the intuition behind these results, which can be represented graphically in Figure 4 where we have, for illustration, decomposed matrix A into columns with vectors a1, a2 and a3. The convex cone spanned by these vectors (i.e. matrix A) is represented by the shaded area X in the diagram.

convex4.gif (4245 bytes)

 

Figure 4 - Minkowski-Farkas Lemma

Let us now see the basic theorem of the alternative. The claim that Ax = b has no non-negative solution x implies that b does not lie in this convex cone, i.e. b Ï X (as is seen in the figure). But then the basic theorem of the alternative claims that this implies there is a y such that yb < 0 and yA ³ 0, i.e. there is a y that forms an obtuse angle with b and an acute angle with every vector ai. It is easy to notice geometrically that this implies that there is a hyperplane H(y, 0) that is orthogonal to y and has the cone X on one side and b on the other (thus H(y, 0) = {x Î Rn | y·x = 0} is separating hyperplane we obtain with the SHT which separates the cone X and the point b. The Minkowski-Farkas Lemma is merely the reverse of this.

Selected References

Kim C. Border (1985) Fixed Point Theorems with Applications to Economics and Game Theory. Cambridge, UK: Cambridge University Press.

Gerard Debreu (1959) Theory of Value: An axiomatic analysis of economic equilibrium. New York: Wiley.

Gerard Debreu (1984) "Economic Theory in a Mathematical Mode", American Economic Review, Vol. 74 (3) p.267-78.

Gerard Debreu (1986) "Theoretic Models: Mathematical form and economic content", Econometrica, Vol. 54 (6), p.1259-70.

Gerard Debreu (1991) "The Mathematization of Economic Theory", American Economic Review, Vol 81 (1), p.1-7.

David Gale (1960) The Theory of Linear Economic Models. New York: McGraw-Hill.

M. Ali Khan (1993) "The Irony In/Of Economic Theory", MLN, Vol. 108 (4), p.759-803.

Philip Mirowski and E. Roy Weintraub (1994) "The Pure and the Applied: Bourbakism comes to America", Science in Context, Vol. 7 (2), p.245-72.

J. von Neumann (1937) "A Model of General Economic Equilibrium", in K. Menger, editor, Ergebnisse eines mathematischen Kolloquiums, 1935-36. 1945 Translation, Review of Economic Studies, Vol. 13 (1), p.1-9.

Hukukane Nikaido (1968) Convex Structures and Economic Theory. New York: Academic Press.

Herbert Scarf (1973) The Computation of Economic Equilibria. (with the collaboration of Terje Hansen), New Haven: Yale University Press.

Akira Takayama (1974) Mathematical Economics. 1985 (2nd) edition, Cambridge, UK: Cambridge University Press.

E. Roy Weintraub (1985) General Equilibrium Analysis: Studies in appraisal. Cambridge, UK: Cambridge University Press.

back Back top Top Selected References

nextNext


Home Alphabetical Index Schools of Thought  Surveys and Essays
Web Links References Contact Frames